package _2022.hot100._101_对称二叉树;


import java.util.Deque;
import java.util.LinkedList;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        this.val=x;
    }
}

/**
 * @author： YHSimon
 * @date： 2022-04-24 15:50
 */
public class Solution {

    //迭代
    public boolean isSymmetric(TreeNode root){
        return check(root,root);
    }

    public boolean check(TreeNode u,TreeNode v){
        Deque<TreeNode> queue=new LinkedList<>();
        queue.offer(u);
        queue.offer(v);
        while(!queue.isEmpty()){
            u=queue.poll();
            v=queue.poll();

            if(u==null&&v==null){
                continue;
            }

            if(u==null||v==null||u.val!=v.val){
                return false;
            }

            queue.offer(u.left);
            queue.offer(v.right);

            queue.offer(u.right);
            queue.offer(v.left);
        }
        return true;
    }


    //递归
    public boolean isSymmetric2(TreeNode root){
        return check2(root,root);
    }

    public boolean check2(TreeNode p,TreeNode q){
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null){
            return false;
        }

        return p.val==q.val&&check2(p.left, q.right)&&check2(p.right, q.left);
    }
}
